package study.sort;

// 归并排序
public class MergeSort {

    public static void main(String[] args) {
        int[] a = {5, -1, 3, 7, -7, 1, 2, 4, 6};
        mergeSort(a, 0, a.length-1);
        for(int i : a){
            System.out.println(i);
        }
    }

    private static void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(a, left, mid );
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    private static void merge(int[] a, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        }

        while (i <= mid) {
            temp[k++] = a[i++];
        }

        while (j <= right) {
            temp[k++] = a[j++];
        }

        for (i = 0; i < k; i++) {
            a[left + i] = temp[i];
        }
    }
}
